// 定义树节点结构
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class SameTree {
    // 判断两棵树是否相同的核心方法
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }

        // 递归遍历左右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    // 根据数组构造二叉树的方法
    public static TreeNode buildTree(Integer[] arr) {
        if (arr.length == 0 || arr[0] == null) return null;

        TreeNode root = new TreeNode(arr[0]);
        java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
        queue.add(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // 构建左子节点
            if (arr[i] != null) {
                current.left = new TreeNode(arr[i]);
                queue.add(current.left);
            }
            i++;

            // 构建右子节点
            if (i < arr.length && arr[i] != null) {
                current.right = new TreeNode(arr[i]);
                queue.add(current.right);
            }
            i++;
        }

        return root;
    }

    // 主方法，程序入口点
    public static void main(String[] args) {

        // 测试用例1：相同的树
        Integer[] arr1 = {1, 2, 3};
        Integer[] arr2 = {1, 2, 3};
        TreeNode tree1 = buildTree(arr1);
        TreeNode tree2 = buildTree(arr2);
        System.out.println("测试用例1结果: " + isSameTree(tree1, tree2)); // 预期输出 true

        // 测试用例2：不同的树
        Integer[] arr3 = {1, 2};
        Integer[] arr4 = {1, null, 2};
        TreeNode tree3 = buildTree(arr3);
        TreeNode tree4 = buildTree(arr4);
        System.out.println("测试用例2结果: " + isSameTree(tree3, tree4)); // 预期输出 false

        // 测试用例3：结构不同的树
        Integer[] arr5 = {1, 2, 1};
        Integer[] arr6 = {1, 1, 2};
        TreeNode tree5 = buildTree(arr5);
        TreeNode tree6 = buildTree(arr6);
        System.out.println("测试用例3结果: " + isSameTree(tree5, tree6)); // 预期输出 false
    }
}